import { TrieNode } from './TrieNode';
import { LogUtil } from '../../../Util/LogUtil';

const TAG: string = 'Trie';
export class Trie {
  static readonly separator: string = '|';

  /** 单词数量 */
  worldCount: number;

  /** 树深度 */
  trieDeepth: number;

  /** 根节点 */
  rootNode: TrieNode;

  /* 单词列表(用于缓存分割结果，优化单个单词判定时重复分割问题) */
  private mWordList: Array<string>;

  /**
   * 构造函数
   */
  constructor() {
    this.worldCount = 0;
    this.trieDeepth = 0;
    this.rootNode = TrieNode.pop('Root', null, this, 0, false);
    this.rootNode.isRoot = true;
    this.mWordList = [];
  }

  /**
   * 添加单词
   * @param word - 要添加的单词
   */
  addWord(word: string) {
    this.mWordList = word.split(Trie.separator);
    const length = this.mWordList.length;
    let node = this.rootNode;
    for (let i = 0; i < length; i++) {
      const spliteWord = this.mWordList[i];
      const isLast = i == length - 1;
      if (!node.containWord(spliteWord)) {
        node = node.addChildNode(spliteWord, isLast);
      } else {
        node = node.getChildNode(spliteWord);
        if (isLast) {
          LogUtil.e(TAG, `添加重复单词:${word}`);
        }
      }
    }
  }

  /**
   * 移除指定单词
   * 仅当指定单词存在时才能移除成功
   * @param word - 要移除的单词
   * @returns 是否成功移除
   */
  removeWord(word: string): boolean {
    if (word == '') {
      // Debug.LogError($"不允许移除空单词!");
      return false;
    }
    const wordNode = this.getWordNode(word);
    if (wordNode == null) {
      // Debug.LogError($"找不到单词:{word}的节点信息，移除单词失败!");
      return false;
    }
    if (wordNode.isRoot) {
      // Debug.LogError($"不允许删除根节点!");
      return false;
    }
    // 从最里层节点开始反向判定更新和删除
    if (!wordNode.isTail) {
      // Debug.LogError($"单词:{word}的节点不是单词节点，移除单词失败!");
      return false;
    }
    // 删除的节点是叶子节点时要删除节点并往上递归更新节点数据
    // 反之只更新标记为非单词节点即可结束
    if (wordNode.childCount > 0) {
      wordNode.isTail = false;
      return true;
    }
    wordNode.removeFromParent();
    // 网上遍历更新节点信息
    let node = wordNode.parent;
    while (node != null && !node.isRoot) {
      // 没有子节点且不是单词节点则直接删除
      if (node.childCount == 0 && !node.isTail) {
        node.removeFromParent();
      }
      node = node.parent;
      // 有子节点则停止往上更新
      if (node.childCount > 0) {
        break;
      }
    }
    return true;
  }

  /**
   * 获取指定字符串的单词节点
   * 只有满足每一层且最后一层是单词的节点才算有效单词节点
   * @param word - 要查找的单词
   * @returns 单词节点
   */
  getWordNode(word: string): TrieNode {
    if (word == '') {
      // Debug.LogError($"无法获取空单词的单次节点!");
      return null;
    }
    // 从最里层节点开始反向判定更新和删除
    const wordArray = word.split(Trie.separator);
    let node = this.rootNode;
    for (let i = 0; i < wordArray.length; i++) {
      const childNode = node.getChildNode(wordArray[i]);
      if (childNode != null) {
        node = childNode;
      } else {
        break;
      }
    }
    if (node == null || !node.isTail) {
      // Debug.Log($"找不到单词:{word}的单词节点!");
      return null;
    }
    return node;
  }

  /**
   * 有按指定单词开头的词语
   * @param word - 要查找的单词前缀
   * @returns 是否存在以该前缀开头的单词
   */
  startWith(word: string): boolean {
    if (word == '') {
      return false;
    }
    this.mWordList = word.split(Trie.separator);
    return this.findWord(this.rootNode, this.mWordList);
  }

  /**
   * 查找单词
   * @param trieNode - 当前节点
   * @param wordList - 单词列表
   * @returns 是否存在该单词
   */
  findWord(trieNode: TrieNode, wordList: Array<string>): boolean {
    if (wordList.length == 0) {
      return true;
    }
    const firstWord = wordList[0];
    if (!trieNode.containWord(firstWord)) {
      return false;
    }
    const childNode = trieNode.getChildNode(firstWord);
    wordList.splice(0, 1);
    return this.findWord(childNode, wordList);
  }

  /**
   * 单词是否存在
   * @param word - 要查找的单词
   * @returns 是否存在该单词
   */
  containWord(word: string): boolean {
    if (word == '') {
      return false;
    }
    this.mWordList = word.split(Trie.separator);
    return this.matchWord(this.rootNode, this.mWordList);
  }

  /**
   * 匹配单词(单词必须完美匹配)
   * @param trieNode - 当前节点
   * @param wordList - 单词列表
   * @returns 是否完美匹配该单词
   */
  matchWord(trieNode: TrieNode, wordList: Array<string>): boolean {
    if (wordList.length == 0) {
      return trieNode.isTail;
    }
    const firstWord = wordList[0];
    if (!trieNode.containWord(firstWord)) {
      return false;
    }
    const childNode = trieNode.getChildNode(firstWord);
    wordList.splice(0, 1);
    return this.matchWord(childNode, wordList);
  }

  /**
   * 获取所有单词列表
   * @returns 所有单词列表
   */
  getWordList(): Array<string> {
    return this.getNodeWorldList(this.rootNode, '');
  }

  /**
   * 获取节点单词列表
   * @param trieNode - 当前节点
   * @param preFix - 前缀
   * @returns 节点单词列表
   */
  private getNodeWorldList(trieNode: TrieNode, preFix: string): Array<string> {
    const wordList = [];
    trieNode.childNodesMap.forEach((v, k) => {
      let word: string;
      if (preFix == '') {
        word = k;
      } else {
        word = preFix + Trie.separator + k;
      }
      if (v.isTail && v.isActive) {
        wordList.push(word);
      }
      if (v.childNodesMap.size > 0) {
        const childNodeWorldList = this.getNodeWorldList(v, word);
        wordList.push(...childNodeWorldList);
      }
    });
    return wordList;
  }

  /**
   * 获取指定字符串的单词节点
   * 只有满足每一层且最后一层是单词的节点才算有效单词节点
   * @param word - 要查找的单词
   * @returns 单词节点列表
   */
  getWordAboutList(word: string): Array<string> {
    if (word == '' || !this.rootNode.isActive) {
      // Debug.LogError($"无法获取空单词的单次节点!");
      return [];
    }
    // 从最里层节点开始反向判定更新和删除
    const wordArray = word.split(Trie.separator);
    let node = this.rootNode;
    for (let i = 0; i < wordArray.length; i++) {
      const childNode = node.getChildNode(wordArray[i]);
      if (childNode != null) {
        node = childNode;
      } else {
        break;
      }
    }
    if (node == null || !node.isTail || !node.isActive) {
      // Debug.Log($"找不到单词:{word}的单词节点!");
      return [];
    }
    return this.getNodeWorldList(node, word);
  }

  /**
   * 判断节点是否启用
   * @param word - 要查找的单词
   * @returns 节点是否启用
   */
  getWordNodeActive(word: string): boolean {
    if (word == '' || !this.rootNode.isActive) {
      // 无法获取空单词的单次节点!
      return false;
    }
    // 从最里层节点开始反向判定更新和删除
    const wordArray = word.split(Trie.separator);
    let node = this.rootNode;
    for (let i = 0; i < wordArray.length; i++) {
      const childNode = node.getChildNode(wordArray[i]);
      if (childNode != null && childNode.isActive) {
        node = childNode;
      } else {
        return false;
      }
    }
    if (node == null || !node.isTail || !node.isActive) {
      // Debug.Log($"找不到单词:{word}的单词节点!");
      return false;
    }
    return true;
  }

  /**
   * 设置节点是否启用
   * @param word - 要设置的单词
   * @param boo - 是否启用
   * @returns 受影响的单词列表
   */
  setWordNodeActive(word: string, boo: boolean): Array<string> {
    if (word == '') {
      // 无法获取空单词的单次节点!
      return null;
    }
    // 从最里层节点开始反向判定更新和删除
    const wordArray = word.split(Trie.separator);
    let node = this.rootNode;
    for (let i = 0; i < wordArray.length; i++) {
      const childNode = node.getChildNode(wordArray[i]);
      if (childNode != null) {
        node = childNode;
      } else {
        break;
      }
    }
    if (node == null || !node.isTail) {
      // Debug.Log($"找不到单词:{word}的单词节点!");
      return null;
    }
    if (node.isActive != boo) {
      node.isActive = boo;
      return this.getNodeWorldList(node, word);
    }
    return null;
  }
}
